home *** CD-ROM | disk | FTP | other *** search
/ Freaks Macintosh Archive / Freaks Macintosh Archive.bin / Freaks Macintosh Archives / Textfiles / zines / hir / hir5 Folder.sit / hir5 Folder / HIR5-7.TXT < prev    next >
Text File  |  1998-04-23  |  6KB  |  118 lines
  1. .........,.........,.........,.........,.........,.........,.........,.......|
  2. [eqAhy3Hu79.Lt0ferW!zP6}  RSA Public Key Encryption  {3islX4bQheu%Lgp1Wfg;Gm2]
  3.                                  By Frogman
  4.  
  5. 'Tis time you all got a dose of crypto fer your own use.  With this little
  6. explination, you will get a quick understanding of how simple, yet how
  7. complex RSA (and with IDEA: PGP) is.
  8.  
  9. So, this info comes to me from Bruce Bosworths' "Codes, Ciphers, and
  10. Computers.  An Introduction to Information Security." Copyright 1982
  11. ISBN 0-8104-45149-2
  12. Lib. O' Congress Z103.b58
  13. Dewey Decimal!!! 001.54'36
  14.  
  15. If you can not find the book with that information, you're screwed.  With
  16. the big stink the govt. is putting out about crypto being too powerful, I
  17. felt it was time for an article about a cryptosystem published 15 years ago,
  18. and designed 20 years ago.  Ronald Rivest, Adi Shamir, and Len Adelman are
  19. the MIT dudes who wrote "A Method for Obtaining Digital Signatures and
  20. Public-Key Cyptosystems" in the MIT Technical Memo LCS/TM82, in April, 1977.
  21. Their combined lastname initials, R. S. A., are how the algorithm got its
  22. name.  I'll try to skip the plaintext, crytotext blahblahblah, because for
  23. now, I'm just giving you the algo.  I'm about up to my ears in stuff to do,
  24. and don't have the time to get much code churned out.  I'll just follow the
  25. book, and 'splain the algo, and give an example.
  26.  
  27. The Math Bits:
  28. We're gonna need some algebra level math, but it's nothing that can't be
  29. done pretty easily with some programming work.
  30.  
  31. Prime numbers are the heart of this whole thing!  For those who were asleep
  32. that day in math class, or each day for each level you took (I had this con-
  33. cept beat into my head every year from 4th grade division to 12th grade
  34. calculus) I'll explain.  You may know that division is multiplications tricky
  35. friend, and that it sometimes (read most of the time) will give you a frac-
  36. tion or decimal if your numbers don't divide evenly.  A prime number is one
  37. that can be divided by every number between itsself and one, and no number
  38. will give you a nice whole answer.
  39.  
  40. The Greatest Common Divisor is the biggest number that you can divide two
  41. numbers by, and get a whole answer for both.
  42.  
  43. Modular Arithmetic is a way of defining that we want the remainder of a pair
  44. of numbers.  Umm... b (mod a) = c would look like:
  45.  a / b == d, Remain c
  46.  
  47. Now, We Start:
  48.  
  49. Everyone needs three numbers to create a keyset for RSA.  Two must be prime,
  50. and for a higher level of security, the bigger they must be.  The third is
  51. a big number.  Pick it at random, though it is recommended to pick either 
  52. 3 or 65536, because that part of the key is in the public key, and doesn't 
  53. really matter.  
  54. When you hear about 48-bit, 56-bit, and 64-bit+ encryption, you are hearing 
  55. about the number of 1s and 0s that are in the binary numbers the crypto 
  56. programs use (ie. pretty big).  Most systems use a 32-bit address to specify 
  57. the location of up to four gigs of RAM.  With a 48-bit number, you can 
  58. address 281,474,976,710,656 locations.  Yes, that is trillions.  And with 
  59. that many choices, one can find a good number of prime numbers.  Imagine 
  60. what you can do with a number in the range of a 128-bit number: 340,282,366,
  61. 920,938,463,463,374,607,431,768,211,456 possibilities.  If you want a load of
  62. choices, w/ a 1000-bit code you got: 107150860718626732094842504906000181056
  63. 14048117055336074437503883703510511249361224931983788156958581275946729175
  64. 53146825187145285692314043598457757469857480393456777482309854210746050623
  65. 71141877954182153046474983581941267398767559165543946077062914571196477686
  66. 542167660429831652624386837205668069376!!!  Fuck it, my fingers are getting 
  67. sick of it... But it's a bitch of a long number, 302 digits, and I do not
  68. feel like double checking them either.
  69.  
  70. To make a keyset we do the math.  The numbers used are labeled as follows:
  71. p1 = one of the <p>rimes
  72. p2 = the other
  73. e = the <e>xtra number 
  74.  
  75. The public key is the easiest:
  76. Multiply your two prime numbers and find n.
  77. p1 * p2 = n
  78. The public key you give to your buddies is (e,n), though with PGP, your key
  79. is encrypted with RSA, and the encrypted key is used for IDEA encryption.
  80. Is know as a KEK, or a Key Encrypting Key.
  81.  
  82. The secret key is found with:
  83. d = GCD((p1-1)*(p2-1))*((p1-1)*(p2-1))+1
  84.     ------------------------------------
  85.                       e
  86.  
  87.  
  88. (d,n) will be your secret key.
  89.  
  90. Now we gotta check and see if the math and all was right (error correction
  91. rules!)
  92. Check and see if:
  93. 1 = e * d (mod ((p1-1)*(p2-1)))
  94.  
  95. Okay, so let's find out how to crypt everything:
  96. Use a number to represent every character in the message.  Hrm.. what set of
  97. numbers is an American standard, and is used alot internationally anyway??
  98. Could it be our old friend, the American Standard Code for Information 
  99. Interchange??  Gee, lets use a 6-bit number, and assign a character to each
  100. one, that gets rid of most of those odd chars... look at RFC1113 for the
  101. pofficial list.
  102.  
  103. m = char number
  104. c = char number spit out after formula
  105. Take your number, use a public key and run it through the formula as such:
  106. c = m^e (mod n)
  107. Change all your numbers to letters, send the text to your 
  108.  
  109. And to get back what you send, your friend would do the same thing, with
  110. their secret key:
  111. m = c^d (mod n)
  112. And change all the numbers back to letters, and read your plans for world
  113. domination, or the answers to that math quiz he's taking 6th hour, that you 
  114. took 2nd...
  115.  
  116. So, with that basic intro to the algo, I'll end.  For another article, I'll
  117. give some refinements, and show some code.
  118.